Chapter 8

Sets and Combinatorics

8.1

The Notion of Set

Set is a fundamental, abstract notion. A set is defined as a collection of objects, which

are called the elements or points of the set. The notions of union (upper A union upper BA ∪B, whereupper AA and

upper BB are each sets), intersection (upper A intersection upper BA ∩B), and complement (upper A Superscript cAc) correspond to everyday

usage. Thus, if upper A equals StartSet a comma b EndSetA = {a, b} and upper B equals StartSet b comma c EndSetB = {b, c}, upper A union upper B equals StartSet a comma b comma c EndSetA ∪B = {a, b, c}, upper A intersection upper B equals StartSet b EndSetA ∩B = {b}, and

upper A Superscript c Baseline equals StartSet c comma d comma ellipsis comma z EndSetAc = {c, d, . . . , z} if our world is the English alphabet. Functions can be thought of

as operations that map one set onto another.

Typically, all the elements of a set are of the same type; for example, a set called

“apples” may contain apples of many different varieties, differing in their colours

and sizes, but no oranges or mangoes; a set called “fruit” could, however, contain all

of these, but no meat or cheese.

One is often presented with the problem of finding or estimating the size of a

set. Size is the most basic attribute, even more basic than the types of elements.

If the set is small, the elements can be counted directly, but this quickly becomes

tedious and, as the set becomes large, it may be unnecessary to know the exact size.

Hence, computational shortcuts have been developed, which are usually labelled

combinatorics. Combinatorial problems are often solved by looking at them in just

the right way and, at an advanced level, problems tend to be solved by clever tricks

rather than the application of general principles.

Problem. Draw Venn diagrams corresponding to intersection∩, union∪, and complement.

8.2

Combinatorics

Most counting problems can be cast in the form of making selections, of which there

are four basic types, corresponding to with or without replacement, each with or

without ordering. This is equivalent to assembling a collection of balls by taking

them from boxes containing different kinds of balls.

© Springer Nature Switzerland AG 2023

J. Ramsden, Bioinformatics, Computational Biology,

https://doi.org/10.1007/978-3-030-45607-8_8

93